斐波那契数列： https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?
// 迭代方案
class Solution {
public:
    int Fibonacci(int n) {
        if (n == 0)
            return 0;
        int first = 1;
        int second = 1;
        int third = 1;
        while (n > 2) {
            third = first + second;
            first = second;
            second = third;
            n--;
        }
        return third;
    }
};

// 递归方案
// 直接用最简单的方式因为代码空间复杂度过高，过不了OJ，所以我们可以采用map进行“剪枝
class Solution {
private:
    unordered_map<int, int> filter;

public:
    int Fibonacci(int n) 
    {
        if (n == 0 || n == 1)
        {
            return n;
        }
        int pre = 0;
        if (filter.find(n - 1) == filter.end()) 
        {
            pre = Fibonacci(n - 1);
            filter.insert({n - 1, pre});
        } 
        else 
        {
            pre = filter[n - 1];
        }
        int ppre = 0;

        if (filter.find(n - 2) == filter.end()) 
        {
            ppre = Fibonacci(n - 2);
            filter.insert({n - 2, ppre});
        } 
        else 
        {
            ppre = filter[n - 2];
        }
        return pre + ppre;
    }
};